package com.lsa.skienna.challenge.chap4.the110405_ShoomakerProblem;

import java.io.File;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import junit.framework.TestCase;

import org.apache.commons.io.FileUtils;

import com.lsa.helpers.Utils;
import com.lsa.shenn.common.perm.PermNoRepeat;
import com.lsa.skienna.challenge.chap4.the110405_ShoomakerProblem.ShoomakerProblem.ShoomakerOrder;
import com.lsa.skienna.challenge.chap4.the110405_ShoomakerProblem.ShoomakerProblem.Task;
import com.lsa.skienna.challenge.chap4.the110405_ShoomakerProblem.ShoomakerProblem.TaskReader;

public class Test_ShoomakerProblem extends TestCase {
	public void test1() throws Throwable {
		File inpFile = new File("data/pc4/110405_ShoomakerProblem/test.inp");
		testBestOrdering(inpFile);
	}
	
	public void testGenerated() throws Throwable {
		String generatedTask = generateTask();
		File inpFile = new File("data/pc4/110405_ShoomakerProblem/generated.inp");
		FileUtils.write(inpFile, generatedTask);
		
		testBestOrdering(inpFile);
	}
	
	public void atestRepeated() throws Throwable {
		
	}

	static void testBestOrdering(File inpFile) throws Throwable {
		TaskReader taskReader = new TaskReader(new FileInputStream(inpFile));
		Task task;
		
		while( (task = taskReader.readNextTask()) != null) {
			testBestOrdering(task);
		}
	}

	public static void testBestOrdering(Task task) {
		PermNoRepeat pnr = new PermNoRepeat(task.orders.length);
		int[] permut = pnr.createFirstSequence();
		
		List<ShoomakerOrder[]> orderSeqs = new ArrayList<ShoomakerOrder[]>();
		
		do{
			ShoomakerOrder[] orders = new ShoomakerOrder[task.orders.length];
			for (int i = 0; i < permut.length; i++) {
				orders[permut[i] - 1] = task.orders[i];
			}
			orderSeqs.add(orders);
			
			permut = pnr.move2NextSequence(permut);
		}
		while(permut != null);
		
		Collections.sort(orderSeqs, new Comparator<ShoomakerOrder[]>() {
			@Override
			public int compare(ShoomakerOrder[] orderSeq1, ShoomakerOrder[] orderSeq2) {
				return calcPenalty(orderSeq1) - calcPenalty(orderSeq2);
			}
		});
		
		int bestPenalty = calcPenalty(orderSeqs.get(0)); 
		List<ShoomakerOrder[]> bestOrderSeqs = new ArrayList<ShoomakerOrder[]>();
		int i = 0;
		while(bestPenalty == calcPenalty(orderSeqs.get(i))) {
			bestOrderSeqs.add(orderSeqs.get(i));
			++i;
		}
		
		Collections.sort(bestOrderSeqs, new Comparator<ShoomakerOrder[]>() {
			@Override
			public int compare(ShoomakerOrder[] orderSeq1, ShoomakerOrder[] orderSeq2) {
				return compareByNumber(orderSeq1, orderSeq2);
			}
		});
		
		ShoomakerProblem.imposeBestOrdering(task);
		
		assertEquals(true, compareByNumber(bestOrderSeqs.get(0), task.orders) == 0);
	}
	
	static int compareByNumber(ShoomakerOrder[] orderSeq1,
			ShoomakerOrder[] orderSeq2) {
		for (int i = 0; i < orderSeq1.length; i++) {
			int c = orderSeq1[i].number - orderSeq2[i].number;
			if (c != 0) {
				return c;
			}
		}
		return 0;
	}
	
	public void testDebug() throws Throwable {
		
		TaskReader taskReader = new TaskReader(new FileInputStream(new File("data/pc4/110405_ShoomakerProblem/test.inp")));
		Task task = taskReader.readNextTask();
		
		PermNoRepeat pnr = new PermNoRepeat(task.orders.length);
		int[] permut = pnr.createFirstSequence();
		
		List<ShoomakerOrder[]> orderSeqs = new ArrayList<ShoomakerOrder[]>();
		
		do{
			ShoomakerOrder[] orders = new ShoomakerOrder[task.orders.length];
			for (int i = 0; i < permut.length; i++) {
				orders[permut[i] - 1] = task.orders[i];
			}
			orderSeqs.add(clone(orders));
//			calcAndPrintPenalties(orders);
			
			permut = pnr.move2NextSequence(permut);
		}
		while(permut != null);
		
		Collections.sort(orderSeqs, new Comparator<ShoomakerOrder[]>() {
			@Override
			public int compare(ShoomakerOrder[] orderSeq1, ShoomakerOrder[] orderSeq2) {
				for (int i = 0; i < orderSeq1.length; i++) {
					int c = (int)ShoomakerProblem.compare(orderSeq1[i], orderSeq2[i]);
					if (c != 0) {
						return c;
					}
				}
				return 0;
			}
		});
		
		for (ShoomakerOrder[] shoomakerOrders  : orderSeqs) {
			calcAndPrintPenalties(shoomakerOrders);
		}
		System.out.println("--------------");
	}
	
	private String generateTask() {
		StringBuilder sb = new StringBuilder();
		
		sb.append("1\n");
		sb.append("\n");
		
		int taskCount = Utils.random(5, 5);
		sb.append(taskCount+"\n");
		int maxTi = 100;
		int maxSi = 100;
		
		for (int i = 0; i < taskCount; i++) {
			sb.append(Utils.random(1, maxTi) + " " + Utils.random(1, maxSi)+"\n");
		}
		
		return sb.toString();
	}
	
	private static ShoomakerOrder[] clone(ShoomakerOrder[] orders) {
		ShoomakerOrder[] newOrders = new ShoomakerOrder[orders.length];
		for (int i = 0; i < orders.length; i++) {
			try {
				newOrders[i] = orders[i].clone();
			} catch (CloneNotSupportedException e) {
			}
		}		
		return newOrders;
	}
	
	private static int calcPenalty(ShoomakerOrder[] orders) {
		int penaltySum = 0;
		int paidSum = 0;
		
		for (int i = 0; i < orders.length; i++) {
			penaltySum += orders[i].penalty;
		}
		
		for (int i = 0; i < orders.length; i++) {
			penaltySum -= orders[i].penalty;
			int paid = orders[i].completionTime * penaltySum;
			paidSum += paid;
		}
		
		return paidSum;
	}
	
	private static void calcAndPrintPenalties(ShoomakerOrder[] orders) {
		int penaltySum = 0;
		
		int paid = 0;
		int paidSum = 0;
		
		Map<ShoomakerOrder, Integer> order2MinTimeOfOthers 
		= new HashMap<ShoomakerOrder, Integer>();  
		
		for (int i = 0; i < orders.length; i++) {
			int min = 1000;
			
			for (int j = 0; j < orders.length; j++) {
				if (i == j) continue;
				
				if (min > orders[j].completionTime) {
					min = orders[j].completionTime;
				}
			}
			
			order2MinTimeOfOthers.put(orders[i], min);
		}
		
		for (int i = 0; i < orders.length; i++) {
			penaltySum += orders[i].penalty;
//			String after = String.format("(%s) ",
//					orders[i].penalty * order2MinTimeOfOthers.get(orders[i]));
			double score = Utils.round(ShoomakerProblem.score(orders[i]), 0.001);
			String after = "(" + score+") ";
			System.out.print(orders[i].number
					+ after);
			
			int min = 1000;
			
			for (int j = 0; j < orders.length; j++) {
				if (i == j) continue;
				
				if (min > orders[j].completionTime) {
					min = orders[j].completionTime;
				}
			}
			
			order2MinTimeOfOthers.put(orders[i], min);
		}
		
//		for (int i = 0; i < orders.length; i++) {
//			System.out.print(orders[i].number + String.format("(%s)", ));
//		
		System.out.print(" : ");
		
		for (int i = 0; i < orders.length; i++) {
			penaltySum -= orders[i].penalty;
			paid = orders[i].completionTime * penaltySum;
			System.out.print(paid + " ");
			paidSum += paid;
		}
		System.out.println("=" + paidSum);
	}
}
